package com.cnmedicine;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class CombineTool {

	public static void main(String[] args) {
		System.out.println(((int) Math.pow(2, 5) - 1)<<(8-5));
		
		List<String> sourceList = IntStream.range(0, 8).mapToObj(index -> "" + index).collect(Collectors.toList());

		long start = System.currentTimeMillis();
//		getAllIndexCombination(sourceList, 13);
		List<List<String>> resList =getAllIndexCombinationByInt(sourceList, 5);
		System.out.println(">>>>"+(System.currentTimeMillis()-start));
		
		for (List<String> list : resList) {
			System.out.println(String.join(",", list));
		}
		
		
		
//		getAllIndexCombination(sourceList, 5).stream().map(list -> String.join(",", list)).sorted().forEach(System.out::println);
		
		System.out.println("===========================");
//		getAllIndexCombinationByInt(sourceList, 13).stream().map(list -> String.join(",", list)).sorted().forEach(System.out::println);
	}

	private static List<List<String>> getAllIndexCombinationByInt(List<String> sourceList, int combineCount) {
		List<List<String>> allResultList = new ArrayList<>();
		int count = sourceList.size();
		if (count > 31) {
			return allResultList;
		}

		int end = ((int) Math.pow(2, combineCount) - 1) << (count - combineCount);
		int start = (int) Math.pow(2, combineCount) - 1;

		for (int k = start; k <= end; k++) {
			int flag = 1;
			int num = 0;
			while (flag > 0 && flag <= k) {
				if ((flag & k) > 0) {
					num++;
				}
				flag <<= 1;
			}
			if (num == combineCount) {
				List<String> res = new ArrayList<>();
				flag = ((int) Math.pow(2, count)) >> 1;
				for (int i = 0; i < count; i++) {
					if ((flag & k) > 0) {
						res.add(sourceList.get(i));
					}
					flag >>= 1;
				}
				allResultList.add(res);
			}
		}

		return allResultList;
	}

	/**
	 * sourceList: 组合数的来源 combineCount：需要的组合数量，例如5，代表取出元素数量为5的全部组合数
	 */
	private static List<List<String>> getAllIndexCombination(List<String> sourceList, int combineCount) {
		List<List<String>> allResultList = new ArrayList<>();

		List<String> resList = new ArrayList<>();
		if (combineCount <= 0 || combineCount > sourceList.size()) {
			combineCount = sourceList.size();
		}

		innerCombinations(resList, sourceList, 0, combineCount, new ArrayList<>());
		for (String item : resList) {
			String[] arr = item.trim().split(" ");
			allResultList.add(Arrays.asList(arr));
		}

		return allResultList;
	}

	private static void innerCombinations(List<String> resList, List<String> sourceList, int start, int len,
			List<String> comList) {
		if (len == 0) {
			String s = "";
			for (int i = 0; i != comList.size(); i++) {
				s = s + " " + comList.get(i).toString();
			}
			resList.add(s);
			return;

		}

		if (start == sourceList.size()) {
			return;
		}

		comList.add(sourceList.get(start));
		innerCombinations(resList, sourceList, start + 1, len - 1, comList);

		comList.remove(comList.size() - 1);
		innerCombinations(resList, sourceList, start + 1, len, comList);
	}
}
